<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>61. 旋转链表</title>
  </head>
  <body>
    <script>
      // 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

      // 输入：head = [1,2,3,4,5], k = 2
      // 输出：[4,5,1,2,3]

      // 输入：head = [0,1,2], k = 4
      // 输出：[2,0,1]

      /**
       * Definition for singly-linked list.
       * function ListNode(val, next) {
       *     this.val = (val===undefined ? 0 : val)
       *     this.next = (next===undefined ? null : next)
       * }
       */

      function ListNode(val, next) {
        this.val = val === undefined ? 0 : val
        this.next = next === undefined ? null : next
      }

      /**
       * @param {ListNode} head
       * @param {number} k
       * @return {ListNode}
       */
      var rotateRight = function (head, k) {
        // debugger
        if (!head) {
          // 链表为空
          return null
        }
        if (!head.next) {
          // 链表只有一位
          return head
        }
        let link = head
        let len = 1
        while (link.next) {
          // 计算链表长度
          link = link.next
          len++
        }
        let n = 0 // 需往前移动 n 位
        // console.log(k, len)
        if (k === len || k % len === 0) {
          // k 与 len 相等或为 len 的倍数，则不用移动
          return head
        } else if (k < len) {
          // 链表往前移动 len - k 位
          n = len - k
        } else {
          // 链表往前移动 len * Math.ceil(k / len) - k （因为 k 可能大于 len 几倍）
          n = len * Math.ceil(k / len) - k
        }
        link.next = head // 形成循环链表
        let preHead = head // 保存末节点
        // console.log(n)
        while (n > 0) {
          // 需往前移动 n 位
          preHead = head
          head = head.next
          n--
        }
        preHead.next = null // 断开循环链表
        return head
      }

      const head = new ListNode(1)
      const sec = new ListNode(2)
      const a = new ListNode(2)
      head.next = sec
      // sec.next = a
      console.log(rotateRight(head, 5))

      // **************************************

      // var rotateRight = function(head, k) {
      //     if (k === 0 || !head || !head.next) {
      //         return head;
      //     }
      //     let n = 1;
      //     let cur = head;
      //     while (cur.next) {
      //         cur = cur.next;
      //         n++;
      //     }

      //     let add = n - k % n;
      //     if (add === n) {
      //         return head;
      //     }

      //     cur.next = head;
      //     while (add) {
      //         cur = cur.next;
      //         add--;
      //     }

      //     const ret = cur.next;
      //     cur.next = null;
      //     return ret;
      // };

      // 作者：LeetCode-Solution
      // 链接：https://leetcode.cn/problems/rotate-list/solution/xuan-zhuan-lian-biao-by-leetcode-solutio-woq1/
      // 来源：力扣（LeetCode）
      // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    </script>
  </body>
</html>
